package com.wenlin.myproduction.util;

/**
 * @author 文琳
 * @Email 377979485@qq.com
 * @desc 给你一个字符串 s ，它仅包含字符 'a' 和 'b'​​​​ 。
 * <p>
 * 你可以删除 s 中任意数目的字符，使得 s 平衡 。我们称 s 平衡的 当不存在下标对 (i,j) 满足 i < j 且 s[i] = 'b' 同时 s[j]= 'a' 。
 * <p>
 * 请你返回使 s 平衡 的 最少 删除次数。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "aababbab"
 * 输出：2
 * 解释：你可以选择以下任意一种方案：
 * 下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"），
 * 下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。
 * 示例 2：
 * <p>
 * 输入：s = "bbaaaaabb"
 * 输出：2
 * 解释：唯一的最优解是删除最前面两个字符。
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 105
 * s[i] 要么是 'a' 要么是 'b'​ 。​
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @time 2022-08-16 星期二 18:09
 */
public class MinimumDeletionsUtil2 {
    public int minimumDeletions(String s) {
        char[] cs = s.toCharArray();
        int ans = 0, b = 0;
        for (int i = 0; i < cs.length; i++) {
            if (cs[i] == 'b') {
                b++;
            } else if (b > 0) {
                ans++;
                b--;
            }
        }
        return ans;
        //a和b的数量不定。删除次数必定小于等于a、b中的较小的数量
        //做法：掐头去尾——去掉左侧的所有a直到碰到b，去掉右侧所有b直到碰到a
        //得到一串“b……a”这样的字符串，检查其中哪个字母少，就删哪个
        //特别的，字符串长度无法超出65534
//        System.out.println("初始s.length = " + s.length());
//        if (s.length() > 65534) {
//            return 0;
//        }
//        char [] arr = s.toCharArray();
//        int times = 0;
//        int numA;
//        int numB;
//        String strA = s.replaceAll("b", "");
//        numA = strA.length();
//        numB = s.length() - numA;
//        while (s.length() > 0) {
//            if (s.startsWith("a")) {
//                s = s.substring(1);
//                numA--;
//                System.out.println("掐头a");
//            } else if (s.endsWith("b")) {
//                s = s.substring(0, s.length() - 1);
//                numB--;
//                System.out.println("去尾b");
//            } else {
//                System.out.println("na = " + numA);
//                System.out.println("nb = " + numB);
//                if (numB > numA) {
//                    s = s.substring(0, s.length() - 1);//删除a
//                    numA--;
//                    System.out.println("删除a");
//                } else {
//                    s = s.substring(1);//删除b
//                    numB--;
//                    System.out.println("删除b");
//                }
//                times++;
//            }
//        }
//        System.out.println("times = " + times);
//        return times;
    }
}
